| contributor | FMI, Sichere und Zuverlässige Softwaresysteme | ||||||||||||||||
E-Mail an | creator |
Ehrig, Hartmut
| König, Barbara
| date |
2004-02
| description |
30 pages
|
Motivated by recent work on the derivation of labelled transitions
and bisimulation congruences from unlabelled reaction rules, we show
how to solve this problem in the DPO (double-pushout) approach to
graph rewriting. Unlike in previous approaches, we consider graphs
as objects, instead of arrows, of the category under consideration.
This allows us to present a very simple way of deriving labelled
transitions (called rewriting steps with borrowed context) which
smoothly integrates with the DPO approach, has a very constructive
nature and requires only a minimum of category theory. The core part
of this paper is the proof sketch that the bisimilarity based on
rewriting with borrowed contexts is a congruence relation.
| format |
application/pdf
| 1084994 Bytes | |
| identifier | http://www.informatik.uni-stuttgart.de/cgi-bin/NCSTRL/NCSTRL_view.pl?id=TR-2004-01&engl=1 |
| language | eng |
| publisher | Stuttgart, Germany, Universität Stuttgart |
| relation | Technical Report No. 2004/01 |
| source | ftp://ftp.informatik.uni-stuttgart.de/pub/library/ncstrl.ustuttgart_fi/TR-2004-01/TR-2004-01.pdf |
| subject | Semantics of Programming Languages (CR F.3.2) |
| Grammars and Other Rewriting Systems (CR F.4.2) | |
| Specifying and Verifying and Reasoning about Programs (CR F.3.1) | |
| Discrete Mathematics Graph Theory (CR G.2.2) | |
| graph rewriting | |
| graph transformation | |
| bisimulation | |
| transition systems | |
| title | Deriving Bisimulation Congruences in the DPO Approach to Graph Rewriting (Long Version) |
| type | Text |
| Technical Report |